//
// Description: 21. 合并两个有序链表
// Created by Loading on 2025/5/23.
//

#include <bits/stdc++.h>
#include <Utils.h>

using namespace std;

ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
    ListNode *head = nullptr;
    ListNode *node = nullptr;
    while (list1 && list2) {
        int value;
        if (list1->val > list2->val) {
            value = list2->val;
            list2 = list2->next;
        } else {
            value = list1->val;
            list1 = list1->next;
        }

        if (!head) {
            head = node = new ListNode(value);
        } else {
            node->next = new ListNode(value);
            node = node->next;
        }
    }
    // 至多只有一个list未合并完成
    if (!head) { // 初始两个list都为nullptr时
        head = list1 ? list1 : list2;
    } else {
        node->next = list1 ? list1 : list2;
    }

    return head;
}

int main() {
    ListNode *list1 = generateListNode({1, 2, 4});
    ListNode *list2 = nullptr;

    auto head = mergeTwoLists(list1, list2);

    cout << printfListNode(head) << endl;

    return 0;
}
